1. Field of the Invention
The present invention relates to a cache table management technique for routers and relates in particular to management of a cache table when entries are entered or extracted in groups between the forwarding table and cache table.
2. Description of the Related Art
Routers connected to a plurality of networks, carry out communications over different networks. To perform this task, the routers connecting the plurality of networks must transfer (or forward) clusters of communication information (packets)
Routers receive packets input from connected networks at a network interface (hereafter, referred to as “interface”). Based on the transmit destination address contained in the header portion of the received packet, the router searches the forwarding table held by each router, and determines a interface number for transmitting the packet, and forwards the packet to the determined interface.
When a large number of networks are connected to the router and a large number of terminals connected to the network, the forwarding table held by router is on a vast scale so the router forwarding process slows down.
A technology was disclosed in the related art for forwarding and high speed packet processing using cache tables.
In Japanese Patent Laid-Open No. 6-261078, the interface for each router contains a routing table and a cache memory for searching the routing table.
The routing table in the router is written with information indicating whether packets can arrive to the destination network via an interface of the router. Each of entries in the routing table, stores the destination network address, the mask corresponding to each destination network address, the destination network address within the transmission network and the transmission interface number.
The cache memory contains a CAM (Content Addressable Memory) and a correspondence table. The destination network address acquired by the pointer to the applicable entry on the routing table is stored in the CAM. This correspondence table holds entries linked to the CAM entries, and stores pointers for the applicable entry of the routing table.
When searching a routing table once again for the same network address, the network address is first collated with CAM destination network addresses, and when an applicable address is found, a pointer is acquired for a routing table from entries for tables matching links to entries stored in the applicable CAM network address.
Searching of tables is speeded up since destination network addresses having a large search count are stored in the cache memory, and the use of correspondence tables allows reducing the CAM entry size.
However, this technology utilized the complete match search method containing a host address as the search key for making table searches of the cache memory. Consequently, this technology had the problems that too much time was required for searches, and that a huge cache memory was required for raising the hit rate.
Whereupon, in EP-A-1035687 describes a router including a forwarding table capable of being longest prefix match searched and a cache table capable of being longest prefix match searched.
The respective table structures and search methods for this technology are first explained. In a first structural example, a forwarding table has entries containing all paths needed in the routing, and a cache table stores a portion of the forwarding table entries. In a second structural example, a cache memory stores a portion of the forwarding table entries and the forwarding table stores all required entries except for those stored in the cache table.
An operation to enter and extract entries from the cache table and forwarding table is necessary in order to raise the cache hit rate. In the first structural example, the entry is copied from the forwarding table to the cache table, and the entry is discarded (deleted) from the cache table to the forwarding table. In the second structural example however, the entry is moved from the forwarding table to the cache table, the entry is also of course, moved from the cache table to the forwarding table. In the following explanation, the copy and delete operations in the first structural example are described. In the case of the second structural example however, the copying in the first structural example is equivalent to moving (operation), while the deletion operation in the first structural example is equivalent to moving. Copying is referred to simply as “input”.
A long search time is required for searching the large quantity of data in the forwarding table. The cache table on the other hand, requires only a short search time though it has only a small data storage capacity. When a search request is made, the cache is first searched for a longest prefix match. If an entry is found in the cache (called “hit”) then the search ends here. However, if an entry is not found (called “mishit”), then a longest prefix match search is then made in the forwarding table. The forwarding table contains all entries, so a search will always find a hit and the search then ends. As also described in, in EP-A-1035687, the longest prefix match is search for matching prefixes from among possible entry candidates and the entry having the longest matching prefix is the hit entry.
When there are for example, four entries having network addresses shown by the prefixes (A) 100.120.0.0/16 (B) 100.0.0 0/8 (C) 100.120.140.0/24 and (D) 100.120.180.0/24, a network address of “100.120.140.5” is assigned as a search key. Here, the 100.120.0.0 are called the prefix bits and numbers punctuated by periods are respectively 8 bits expressed in decimal notation. When a decimal number comprised of these 8 bits is 0 (zero) it signifies an optional (don't care) number. The number after the / signifies the prefix length. A network address of “100.120.140.5” is a match for any of the prefixes (A) (B) and (C) so that (A) (B) and (C) all become search candidates. However, in a longest matching prefix search, the entry having the longest prefix length is selected so that in this case, the longest prefix length equals 24 so that the search result (C) 100.120.140.0/24 is a hit.
Next, the entries input to the cache table are described. In the invention disclosed in EP-A-1035687, the insertion and extraction of entries from the cache table is not the copy or deletion of particular single entries but instead the movement of a plurality or in some cases single entries under specified rules. In other words, the short part of the prefix length for an entry having the same prefix is called the parent and the long part of the prefix length is called the child, and when input to a cache, all of its children are always input together into the cache, and during output from a caches all of its parents are always extracted together from the cache. In the following description, the plurality of entries for movement complying with this system are referred to as entry groups.
A specific example for making an entry group is described next. In the four entries (A) (B) (C) (D) for example, when the entry called (A) 100.120.0.0/16 is moved to the cache from the forwarding table, (A) (C) and (D) become an entry group. Next, when (A) is moved from the cache table to the forwarding table, only (A) becomes an entry group.
When the interface numbers serving as the output path numbers for the above (A) 100.120.0.0/16 (C) 100.120.140.0/24 and (D) 100.120.180.0/24 are different. If only (A) 100.120.0.0/16 is placed in the cache, and a search key of “100.120.140.5” is then applied, the interface number matching (C) should be obtained at the longest prefix match searching result. In this case, however, the interface number matching with (A) is instead obtained from the entries in the cache. Also, when (C) is taken out of the cache and (A) is left in the cache, and the search key of “100.120.140.5” is applied, instead of the interface number matching (C), the interface number matching (A) will be a hit in the cache.
In the cache system, however, since the data to be entered in the cache is a portion of the entire data in the forwarding table, an entry must be selected from the forwarding table and input to the cache. At this time, the cache hit probability must be raised in order to perform a high speed search, so selection of the entry to be placed in the cache is a critical issue. Also, when dynamic changes occur in the contents of the cache entries, the selection of entries to be extracted from the cache also becomes a critical issue.
The LRU (Least Recently Used) method was utilized as a selection method in the forwarding technology in the above two examples. However, even though the LRU method is effective in inputting and extracting individual entries, the LRU has a first problem in that in contrast to the individual entries as in EP-A-1035687, the LRU is not effective for use with entry groups or in other words, under the restriction of inputting and extracting a plurality of related entries in clusters. As shown in FIG. 12 for example, when extracting (C) from a cache containing prefix (A) 100.120.0.0/16 with time sequence “3:00” “2:00”, and prefix (C) 100.120.140.0/24 with time base “1:00” and“0:30”, the (A) or parent is extracted but the (D) prefix having a older time usage than (A) will still remain in the cache.
An algorithm such as the LRU tends to handle data mechanically according the number of times the data is referred to for making a selection, creating a second problem that a criticality (or importance) level cannot be assigned to data as needed or more specifically, that the extent of line connections cannot be easily assigned according to policy or a fee system. For example even in cases where entries have different levels of importance (criticality), the conventional LRU method treats the input and output of all entries from the cache in the same way, so that data cannot be handled according to its level of importance.